package DP;

public class Demo1 {
     //动态规划
    public int Fibonacci(int n) {
        /*1:斐波那契数列*/
        if (n<=2){
            return 1;
        }
        int a=1;
        int b=1;
        int c=0;
        while (n>2){
            c=a+b;
            a=b;
            b=c;
            n--;
        }
        return c;
    }
    public int jumpFloor(int target) {
        /*2:青蛙跳台阶
        * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
        * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。*/
        int a=0;
        int b=1;
        int c=0;
        while (target > 0){
            c=a+b;
            a=b;
            b=c;
            target--;
        }
        return c;
    }
    public int minCostClimbingStairs (int[] cost) {
        /*3:最小花费爬楼梯*/
        //dp[i]表示爬到第i阶楼梯需要的最小花费
        int[] dp = new int[cost.length + 1];
        for(int i = 2; i <= cost.length; i++)
            //每次选取最小的方案
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[cost.length];
    }




    public String LCS(String str1, String str2) {
        int maxLenth = 0;//记录最长公共子串的长度
        //记录最长公共子串最后一个元素在字符串str1中的位置
        int maxLastIndex = 0;
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                //递推公式，两个字符相等的情况
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    //如果遇到了更长的子串，要更新，记录最长子串的长度，
                    //以及最长子串最后一个元素的位置
                    if (dp[i + 1][j + 1] > maxLenth) {
                        maxLenth = dp[i + 1][j+1];
                        maxLastIndex = i;
                    }
                } else {
                    //递推公式，两个字符不相等的情况
                    dp[i + 1][j+1] = 0;
                }
            }
        }
        //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
        return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
    }
    /*进行优化过后的*/
    public String LCS2(String str1, String str2) {
        int maxLenth = 0;//记录最长公共子串的长度
        //记录最长公共子串最后一个元素在字符串str1中的位置
        int maxLastIndex = 0;
        int[] dp = new int[str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            //注意这里是倒叙
            for (int j = str2.length() - 1; j >= 0; j--) {
                //递推公式，两个字符相等的情况
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[j + 1] = dp[j] + 1;
                    //如果遇到了更长的子串，要更新，记录最长子串的长度，
                    //以及最长子串最后一个元素的位置
                    if (dp[j + 1] > maxLenth) {
                        maxLenth = dp[j + 1];
                        maxLastIndex = i;
                    }
                } else {
                    //递推公式，两个字符不相等的情况
                    dp[j + 1] = 0;
                }
            }
        }
        //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
        return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
    }
    public static void main(String[] args) {
        Demo1 demo1=new Demo1();
       String str1="1AB2345CD";
       String str2="12345EF";
       String ret=demo1.LCS(str1,str2);
        System.out.println(ret);



    }
}
